package heap;

import java.util.Arrays;

/**
 * 最大堆实现
 */
public class MaxHeap {
    private int heapSize = 0;
    private int[] heap;

    public MaxHeap(int[] heap) {
        this.heap = heap;
        heapSize = heap.length;
        buildMaxHeap();
    }

    private void maxHeapify(int cur) {
        int left = (cur << 1) + 1;    //2n+1 左孩子结点
        int right = (cur << 1) + 2;    //2n+2 右孩子结点
        int largest = cur;
        if (left < heapSize && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < heapSize && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != cur) {
            int temp = heap[cur];
            heap[cur] = heap[largest];
            heap[largest] = temp;
            maxHeapify(largest);
        }
    }

    private void buildMaxHeap() {
        //(heapSize/2)到(heapSize-1)的元素都是叶结点，每个叶结点都可以看成只包含一个元素的堆
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            maxHeapify(i);
        }
    }

    public void heapSort() {
        for (int i = heapSize; i > 0; i--) {
            int temp = heap[0];
            heap[0] = heap[heapSize - 1];
            heap[heapSize - 1] = temp;
            heapSize--;
            maxHeapify(0);
        }
        System.out.println("堆排序结果：");
        System.out.println(Arrays.toString(heap));
    }

    public void displayMaxHeap() {
        System.out.println("根 左 右");
        for (int i = 0; i < heapSize; i++) {
            System.out.print(heap[i]);
            int l = (i << 1) + 1;
            int r = (i << 1) + 2;
            if (l < heapSize) {
                System.out.print(" " + heap[l]);
            }
            if (r < heapSize) {
                System.out.print(" " + heap[r]);
            }
            System.out.println();
        }
    }
}
